package cn.dlc.com.graph;

import lombok.Data;

/**
 * @author 邓立川
 * @date 2021/3/30 21:27
 * @desc 拓扑排序，检测是否有环
 */
@Data
public class DirectedCycle {

    // 索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    // 记录图中是否有环
    private boolean hasCycle;
    // 索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
    private boolean[] onStack;

    public DirectedCycle(Digraph digraph){
        // 初始化marked数组
        this.marked = new boolean[digraph.getV()];
        // 初始化是否有环
        this.hasCycle = false;
        // 初始化顶点,默认都是false
        this.onStack = new boolean[digraph.getV()];

        for (int i = 0; i < digraph.getV(); i++) {
            // 获取所有的顶点，调用dfs，判断有没有环
            if(!marked[i]) {
                // 依次遍历节点，看看哪个节点会出现一条环路
                dfs(digraph, i);
            }
        }
    }

    // 深度遍历，检测当前节点所有的邻接点，判断是不是有环
    private void dfs(Digraph digraph, int i) {
        // 标记检测
        marked[i] = true;

        // 当前节点检测过了
        onStack[i] = true;

        // 深度遍历,获取邻接点
        for (Integer w : digraph.adj(i)) {
            if(!marked[w]) {
                dfs(digraph, w);
            }

            // 判断当前节点是不是已经进来过了
            if(onStack[w]) {
                // 有环
                this.setHasCycle(true);
                return ;
            }
        }
        // 检测过了，标记为false，很重要
        onStack[i] = false;
        // 没有环
        this.setHasCycle(false);
    }

    public boolean hasCycle(){
        return hasCycle;
    }
}
